The present invention generally relates to a method and system for accessing hierarchically arranged data, and more specifically, to a method and system that enables this type of data to be selectively accessed and viewed in a plurality of different ways on the display screen of a portable computing device.
Efficient, quick access to data is one of the driving forces behind the rapid increase in popularity of the World Wide Web and the Internet. However, until access to the Internet via portable devices such as cell phones or personal data assistants (PDAs) becomes more available, more reliable, and sufficiently low in cost, it will generally be preferable to provide access to needed data that are simply stored in the electronic memory of a PDA or other such portable computing device. A relatively large amount of data of interest to an individual can be stored in a few megabytes of memory in such devices. Indeed, so much data can be loaded into memory that accessing a desired portion of the data can be somewhat difficult using conventional browsing techniques or using an indexed data search.
The most logical way to organize data to facilitate rapid and efficient retrieval of desired facts is to first arrange the data in a rational hierarchical structure that is organized along the lines in which people typically think when xe2x80x9czeroing inxe2x80x9d on a desired piece of information. It will generally be easier for a user to view a limited number of subjects at the highest level of the hierarchy, select one of the subjects that seems most relevant to the desired information, and then select a category under the selected subject that seems most relevant. These steps can then be repeated one or more times, enabling the access of successively lower levels of the hierarchy, and ultimately should yield the specific information being sought by the user.
While it is possible to organize data in such a logical hierarchical structure so that it can be readily located in the above-described manner, it can sometimes be more efficient to employ an alphabetically ordered subcategory index to locate the desired information. However, a topic that is selected from such an ordered index may be closely related to the desired information, but not include the actual data of interest. Also, note that a subcategory list displayed as a result of an index search may include subcategories that differ from a subcategory list displayed as a result of a hierarchical search.
An example can help to clarify the preceding point. In this example, the data in a database are arranged in a hierarchical relationship and stored in the memory of the portable device. These data include information relating to points of interest, travel, businesses, services, restaurants, etc, for a specific metropolitan city or region. Included under a top level is the subject xe2x80x9cBusiness and Government.xe2x80x9d Under that subject are second level categories that include the following: xe2x80x9cAssociations;xe2x80x9d xe2x80x9cBanks and Brokerages;xe2x80x9d xe2x80x9cChambers of Commerce;xe2x80x9d xe2x80x9cConvention Info;xe2x80x9d xe2x80x9cGovernment Information;xe2x80x9d xe2x80x9cLegal and Courts;xe2x80x9d xe2x80x9cMajor Employers;xe2x80x9d and xe2x80x9cShipping and Supplies.xe2x80x9d A person searching for a financial institution at which to apply for a loan might initially choose the category xe2x80x9cBanks and Brokerages,xe2x80x9d and then choose the next level subcategory xe2x80x9cBanksxe2x80x9d from a list of subcategories that also includes: xe2x80x9cATM""s;xe2x80x9d xe2x80x9cBrokerages;xe2x80x9d xe2x80x9cCredit Card Companies;xe2x80x9d xe2x80x9cCredit Unions;xe2x80x9d xe2x80x9cCurrency Exchange;xe2x80x9d and xe2x80x9cTravelers Checks.xe2x80x9d From the list of banks displayed when this subcategory is selected, the user could then choose a desired bank, causing the display of an address, telephone number, and other pertinent information, or the user could move back to the display of subcategories and choose the subcategory xe2x80x9cCredit Unionsxe2x80x9d to list the available credit unions in the region. Thus, the hierarchical categorization of data enables the user to search through the available categories and find the desired data relatively efficiently, but more importantly, it enables the user to choose from among related subcategories so as to ensure that the desired information is readily displayed.
Alternatively, a user may prefer to search for information using an index that lists subcategories alphabetically. In the prior art, selecting a topic such as xe2x80x9cBanksxe2x80x9d would only result in a list of the banks included in the data being displayed. The hierarchical relationship of the subcategory xe2x80x9cBanks,xe2x80x9d relative to the categories and subjects in the example set forth above, would not be evident from such a list. Clearly, it would be preferable to display the hierarchical category and subject above the subcategory xe2x80x9cBanks,xe2x80x9d since a user would then more readily be able to expand a search into a related subcategory, such as xe2x80x9cCredit Unions,xe2x80x9d to find useful information related to the original index subcategory that was selected. However, since a typical prior art index search does not display the hierarchical levels above a selected index subcategory, the benefits of the hierarchical categorization of the data would be lost by making an index search.
The need to retain and display the hierarchical relationship of data being accessed through an indexed search is particularly relevant to data accessed with a portable device such as a PDA, since such devices have relatively small display screens and can only display a few lines of information at one time. By enabling a user to access hierarchical data through either a hierarchical search or an index search, while retaining and displaying the hierarchical relationships of the data accessed via the index search on the display screen, a user will be able to readily determine if other related subcategories should be viewed to best identify information of interest to the user.
The present invention is directed to a method for enabling a user to search for a desired data element in a database, using either a hierarchical-based search or an index-based search. A database having a plurality of data elements is stored in a device capable of both accepting a user input, and displaying a result to a user. The user is able to search the database for the desired data element by a hierarchical-based search or an index-based search. In response to a user""s selection, a desired data element is displayed to a user, such that a hierarchical relationship of the desired data element to other data elements in the database is also displayed to the a user. Particularly when a user has employed an index-based search, the simultaneous display of the selected data element and hierarchical relationship of the data element to other data elements in the database offers the user the ability to determine, based on the hierarchical relationships displayed, if a different, yet related data element more closely matches a result a user desired. In at least one embodiment, the device is a handheld device, such as a cell phone, a pager, a personal digital assistant, or other compact computing device.
The hierarchical relationship that is displayed is at least a title of hierarchical level that is at a higher level than that to which the desired data element belongs. Preferably, if space on the display permits, all higher hierarchical levels are displayed. If it is not possible to display all higher hierarchical levels, then at least the next two higher levels (relative to that of the desired data element) are preferably displayed. In at least one embodiment, the bottom level of the hierarchy represents database records, a top level of the hierarchy represents a subject level, a second from the top level of the hierarchy represents a category level, and a second from the bottom level of the hierarchy represents a subcategory level.
Preferably, when a data element from the index is displayed, both the subject level and category level are also displayed. When the data element displayed is a database record, the related subject level, the category level, and the subcategory level are also preferably displayed.
In at least one embodiment, when a user has selected a hierarchical-based search, then the user is enabled to navigate the hierarchy, selecting a subject, a category, and a subcategory. While it is anticipated that most databases will include subject, category, and subcategory levels, small databases may be organized using subject and category levels. Also, larger databases may be organized using subject, category, and multiple levels of subcategories.
When a user has selected an index-based search, then the user is enabled to select an item from an indexed list that represents a hierarchical level, which is associated with no lower hierarchical levels, other than database records. The bottom level of the hierarchy represents the data records (names, telephone numbers, addresses, image data, etc.). Depending on the depth of the hierarchy, the next highest level might be either a subcategory, a category, or even a subject. For example, in some hierarchical databases, one element in a first hierarchical subject level might lead to three category elements in a second hierarchical category level. Of those three category elements in the second hierarchical category level, one category element may not have any subcategories associated with it. Selecting that category element would result in the listing summarizing all related data from the lowest hierarchical level (i.e., the database records). Thus, that category element represents a hierarchical level, which is second from the bottom of the hierarchy, and as such, that category element would be included in the index. Similarly, if selecting a particular subcategory element leads to the display of additional subcategories, rather than the listing summarizing the data from the lowest hierarchical level, that particular subcategory element does not represent a hierarchical level second from the bottom of the hierarchy. Therefore, that particular subcategory would not be included in the index. When a category or a subcategory is selected from the indexed list, the higher hierarchical levels for that category or subcategory item are also displayed. It should be understood that this concept extends to the first hierarchical subject level as well. While in most hierarchical databases, selecting a subject element from the first hierarchical subject level will lead to the display of at least one category element from a second hierarchical category level, it is conceivable that instead, selecting that subject element would result in the display of a listing summarizing the related data from the lowest hierarchical level. In rare circumstances, a subject element from the first hierarchical subject level can also represent a hierarchical level second from the bottom of the hierarchy and would be included in the index.
Once a user has selected a data element whose hierarchical level represents the second lowest level of the hierarchy (i.e., a data element that is a subject element, a category element, or a subcategory element, and whose selection does not result in the display of one or more category elements or a subcategory elements), a listing summarizing all database record corresponding to that data element is displayed, along with related higher hierarchical levels of the data element. A selection can be made from that listing, resulting in a display of a specific database record.
Preferably the database used in conjunction with the present invention includes a dual data structure comprising a first tree data structure that defines a hierarchical relationship between the plurality of data elements in the database, and a second data structure comprising an ordered array. The first tree data structure includes at least one pointer associated with any node having at least one of a first child, a next sibling, and a parent, such that for each such node, the pointer refers to any one of the first child, the next sibling, and the parent associated with that node. Such a tree data structure preferably includes at least two types of nodes, a first hierarchical type of node comprising at least one of a subject node, a category node, and a subcategory node; and a second data record type of node comprising either an individual data element or a database record.
The ordered array is generated from the contents of the hierarchical level that is immediately adjacent to the lowest hierarchical level of the hierarchy described in the tree data structure. The contents of the ordered array are organized in a desired order. In at least one embodiment, the ordered array is alphabetized. Preferably the ordered array is stored in a memory associated with the computing device, in a sequential order corresponding to the desired order.
In another embodiment, an attribute is assigned to each element of the ordered array and defines a position of each element in the ordered array, such that the attributes are used to determine an order with which each element of the ordered array is displayed to a user.
The dual data structure enables a user to make a selection from a plurality of hierarchical ranked subjects, to make a selection from a plurality of hierarchical ranked categories based on a user selected subject, to make a selection from a plurality of hierarchical ranked subcategories based on a user selected category, and to make a selection of a subcategory from a plurality of indexed subcategories. Preferably the desired data are read in place.
In at least one embodiment, a user can add data related to the database. Preferably the user added data are stored as a separate database, and not incorporated or integrated into the indexed array data. When a user selects a hierarchical level associated with a user added data element, the data element is displayed at a top of a list of data elements associated with the hierarchical level selected by a user. By separating the user added data, both the tree data structure and the ordered array can be updated or moved to a different device without changing or simultaneously moving the user added data.
Another aspect of the present invention is directed to an article of manufacture adapted for use with a computing device. The article includes a memory medium and a plurality of machine instructions stored on the memory medium, which when executed by a computing device, cause the computing device to carry out functions generally consistent with the steps of the method described above. Such memory media can be either or both integral to the article, or a removable memory media.
Yet another aspect of the present invention is directed to a system having a memory in which a plurality of machine instructions are stored, a display, a user input device, and a processor that is coupled to the display and to the memory to access the machine instructions. The processor executes the machine instructions and thereby implements a plurality of functions that are generally consistent with the steps of the method described above.
Still another aspect of the invention is directed to a database having a dual data structure. The elements of the dual structure for the database are generally consistent with above description.
A still further aspect of the present invention relates to a method for producing a dual data structure from unorganized data. The unorganized data are first grouped into a plurality of data elements, preferably into database records. Then, hierarchical relationships between the plurality of data elements are generated, preferably including a top subject level, an intermediate category level, and a subcategory level. The tree is constructed such that a top level of the hierarchy is a subject level, a second level of the hierarchy is a category level, a third level of the hierarchy is a subcategory level, and a bottom level of hierarchy corresponds to records of the data. As the tree data structure is constructed, the pointers described above are included. An ordered array is generated based on the those data elements of the subject level, the category level, and any subcategory levels that are not associated with a lower category level or subcategory level. Such data elements are only associated with a lower hierarchical level that includes the database records, and as such, those data elements (regardless of whether they are elements of the subject level, the category level, or a subcategory level) can be considered to be immediately above the level of the records. The array is ordered according to a desired ordering paradigm, such as alphabetically, or hierarchically.